/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package algoristhm;

import Objects.Square;
import java.util.ArrayList;

/**
 *
 * @author William
 */
public class Astar2 {

    public static double heuristic(int x, int y, int fX, int fY) {
        return (Math.abs(fX - x) + Math.abs(fY - y) )*10;
    }
    private Square start;
    private Square finish;
    private int found;//0 la chua thay, 1 la thay
    private ArrayList<Square> route;
    Square[][] tree;
    private priorityQueue openSet;
    private priorityQueue closedSet;

    public Astar2(Square[][] tree, Square start, Square finish) {
        this.tree = tree;
        this.start = start;
        this.finish = finish;
        this.found = 0;
        route = new ArrayList<>();
        openSet = new priorityQueue();
        closedSet = new priorityQueue();
        
    }

    //xu ly node hien tai
    /*
     cho node vao node list
     xet 8 node xung quanh no, cho vao queue
    
     */
    public ArrayList<Square> getNeighbor(Square current) {
        ArrayList<Square> neighbor = new ArrayList<>();
        int fX = finish.getXx();
        int fY = finish.getYy();
        int sX = current.getXx();
        int sY = current.getYy();
        //tren
        if (sY > 0) {
            if (tree[sX][sY - 1].getStatus() != 10) {
                tree[sX][sY - 1].setHn(heuristic(sX, sY - 1, fX, fY));
                tree[sX][sY - 1].setGn(current.getGn()+ 10+tree[sX][sY - 1].getTime());
                neighbor.add(tree[sX][sY - 1]);
//                status =/ 1;
            }

        }
        //tren trai
        if (sY > 0 && sX > 0 && tree[sX][sY - 1].getStatus() != 10 && tree[sX - 1][sY].getStatus() != 10) {
            if (tree[sX - 1][sY - 1].getStatus() != 10) {
                tree[sX - 1][sY - 1].setHn(heuristic(sX - 1, sY - 1, fX, fY));
                tree[sX - 1][sY - 1].setGn(current.getGn()+ 14+tree[sX - 1][sY - 1].getTime());
                neighbor.add(tree[sX - 1][sY - 1]);
//                status = 1;
            }
        }
        //tren phai
        if (sY > 0 && sX < 19 && tree[sX][sY - 1].getStatus() != 10 && tree[sX + 1][sY].getStatus() != 10) {
            if (tree[sX + 1][sY - 1].getStatus() != 10) {
                tree[sX + 1][sY - 1].setHn(heuristic(sX + 1, sY - 1, fX, fY));
                tree[sX + 1][sY - 1].setGn(current.getGn()+ 14+tree[sX + 1][sY - 1].getTime());
                neighbor.add(tree[sX + 1][sY - 1]);
//                status = 1;
            }
        }
        //trai
        if (sX > 0) {
            if (tree[sX - 1][sY].getStatus() != 10) {
                tree[sX - 1][sY].setHn(heuristic(sX - 1, sY, fX, fY));
                tree[sX - 1][sY].setGn(current.getGn()+ 10+ tree[sX - 1][sY].getTime());

                neighbor.add(tree[sX - 1][sY]);
//                status = 1;
            }
        }
        //phai
        if (sX < 19) {
            if (tree[sX + 1][sY].getStatus() != 10) {
                tree[sX + 1][sY].setHn(heuristic(sX + 1, sY, fX, fY));
                tree[sX + 1][sY].setGn(current.getGn()+ 10+tree[sX + 1][sY].getTime());
  
                neighbor.add(tree[sX + 1][sY]);
//                status = 1;
            }
        }
        //duoi
        if (sY < 19) {
            if (tree[sX][sY + 1].getStatus() != 10) {
                tree[sX][sY + 1].setHn(heuristic(sX, sY + 1, fX, fY));
                tree[sX][sY + 1].setGn(current.getGn()+ 10+tree[sX][sY + 1].getTime());
                neighbor.add(tree[sX][sY + 1]);
//                status = 1;
            }
        }
        //duoi phai
        if (sY < 19 && sX < 19 && tree[sX+1][sY].getStatus() != 10 && tree[sX][sY + 1].getStatus()!=10) {
            if (tree[sX + 1][sY + 1].getStatus() != 10) {
                tree[sX + 1][sY + 1].setHn(heuristic(sX + 1, sY + 1, fX, fY));
                tree[sX + 1][sY + 1].setGn( current.getGn()+14+tree[sX + 1][sY + 1].getTime());

                neighbor.add(tree[sX + 1][sY + 1]);
//                status = 1;
            }
        }
        //duoi trai
        if (sY < 19 && sX > 0 && tree[sX][sY + 1].getStatus() != 10 && tree[sX - 1][sY].getStatus() != 10) {
            if (tree[sX - 1][sY + 1].getStatus() != 10) {
                tree[sX - 1][sY + 1].setHn(heuristic(sX - 1, sY + 1, fX, fY));
                tree[sX - 1][sY + 1].setGn(current.getGn()+ 14+tree[sX - 1][sY + 1].getTime());

                neighbor.add(tree[sX - 1][sY + 1]);
//                status = 1;
            }
        }
        return neighbor;
    }

    public ArrayList<Square> findPath() {
        int a=0;
        openSet.enQueue(start);
        start.setFather(null);
        start.setGn(0);
        start.setHn(heuristic(start.getXx(), start.getYy(), finish.getXx(), finish.getYy()));
        int fX = finish.getXx();
        int fY = finish.getYy();
        Square current;
        while (openSet.isEmpty() == false) {
            
            //lay o co fn be nhat trong openlist
            current = openSet.deQueue();
            int sX = current.getXx();
            int sY = current.getYy();
            
            //kiem tra o do co phai dich ko
            if (sX == fX && sY == fY) {
                ArrayList<Square> b= recontructPath(current);
                return b;
            }
            //dua o da xet vao closed list
            closedSet.enQueue(current);
            
            ArrayList<Square> neighborNodes = getNeighbor(current);
            for (int i = 0; i < neighborNodes.size(); i++) {
                if (closedSet.contain(neighborNodes.get(i)) == true) {
                    continue;
                }
                int g;
                if (Math.abs(current.getXx()-neighborNodes.get(i).getXx())==1 && Math.abs(current.getYy()-neighborNodes.get(i).getYy())==1){
                    g=14;
                }else{
                    g=10;
                }
                double tentativeGn = current.getGn() + g + neighborNodes.get(i).getTime();
                if (openSet.contain(neighborNodes.get(i)) == false || tentativeGn < neighborNodes.get(i).getGn()) {
                    neighborNodes.get(i).setFather(current);
                    neighborNodes.get(i).setGn(tentativeGn);
                    neighborNodes.get(i).setHn(heuristic(neighborNodes.get(i).getXx(), neighborNodes.get(i).getYy(), fX, fY));
                    if (openSet.contain(neighborNodes.get(i)) == false) {
                        openSet.enQueue(neighborNodes.get(i));
                    }
                }
            }
        }
        return null;
    }
    
    public ArrayList<Square> recontructPath(Square current){
        ArrayList<Square> path= new ArrayList<>();
        path.add(current);
        while (current.getFather()!=null){
            current=current.getFather();
            path.add(current);
        }
        return path;
    }
    
    public int getFound() {
        return found;
    }

    public void setFound(int found) {
        this.found = found;
    }

    public ArrayList<Square> getRoute() {
        return route;
    }

}
